package com.lw.leetcode.binary.b;

/**
 * Created with IntelliJ IDEA.
 * 1894. 找到需要补充粉笔的学生编号
 *
 * @author liw
 * @version 1.0
 * @date 2021/9/10 9:11
 */
public class ChalkReplacer {


    public int chalkReplacer(int[] chalk, int k) {
        int end = chalk.length - 1;
        long[] arr = new long[end + 1];
        arr[0] = chalk[0];
        for (int i = 1; i <= end; i++) {
            arr[i] = arr[i - 1] + chalk[i];
        }
        k %= arr[end];
        int st = 0;
        while (st < end) {
            int m = st + ((end - st) >> 1);
            if (arr[m] > k) {
                end = m;
            } else {
                st = m + 1;
            }
        }
        return st;
    }

}
